#include <vector>
#include <numeric>    // For std::min (though <algorithm> also works)
#include <algorithm>  // For std::min
#include <stdexcept>  // For throwing exceptions on invalid input
#include <iostream>   // For potential debugging output

// Define the structure for the output fragments
struct Fragment {
    int length; // Total length of the fragment (header + data)
    int offset; // Offset of this fragment's data relative to the original data, in 8-byte units
};

// Define the fixed IP header size
const int IP_HEADER_SIZE = 20;

/**
 * @brief Simulates IP packet fragmentation along a path with varying MTUs.
 *
 * @param packetLength The total length of the original IP packet (including the 20-byte header).
 * @param pathMTUs A vector of integers representing the MTU (Maximum Transmission Unit)
 *                 of each network segment along the path, in order.
 * @return A vector of Fragment structs, representing the final set of fragments
 *         after traversing the path. Returns an empty vector if the initial packet
 *         has no data or if fragmentation is impossible due to MTU constraints.
 * @throws std::invalid_argument if an MTU value is less than or equal to the IP header size,
 *         or if an MTU doesn't allow for at least 8 bytes of data payload.
 */
std::vector<Fragment> fragmentPacket(int packetLength, const std::vector<int>& pathMTUs) {

    // --- 1. Initial Validation and Setup ---
    if (packetLength <= IP_HEADER_SIZE) {
        // Packet has no data or is invalidly small
        return {}; // Return empty vector
    }

    int initialDataLength = packetLength - IP_HEADER_SIZE;

    // Use an internal structure during processing to keep track of more details easily
    struct ProcessingFragment {
        int dataLength;     // Length of the data payload in this fragment
        int offsetBytes;    // Offset in bytes relative to the original data start
        bool moreFragments; // The More Fragments (MF) flag state for this fragment
    };

    // Start with a single "fragment" representing the original packet's data
    std::vector<ProcessingFragment> currentFrags = {
        {initialDataLength, 0, false} // Original packet has MF=0
    };

    // --- 2. Iterate Through Each Network Segment (MTU) ---
    for (int mtu : pathMTUs) {
        // Validate current MTU
        if (mtu <= IP_HEADER_SIZE) {
            throw std::invalid_argument("MTU (" + std::to_string(mtu) + ") must be greater than IP header size (" + std::to_string(IP_HEADER_SIZE) + ")");
        }

        // Calculate the maximum data payload allowed by this MTU
        int maxDataPayload = mtu - IP_HEADER_SIZE;

        // Adjust maxDataPayload to be the largest multiple of 8 less than or equal to the calculated value
        // This is crucial because the offset field is in units of 8 bytes.
        maxDataPayload = (maxDataPayload / 8) * 8;

        if (maxDataPayload <= 0) {
            // This MTU is too small to carry even the smallest (8-byte aligned) data payload
             throw std::invalid_argument("MTU (" + std::to_string(mtu) + ") does not allow for any 8-byte aligned data payload after header.");
        }

        std::vector<ProcessingFragment> nextFrags; // Store results for this MTU step

        // Process each fragment arriving from the previous step
        for (const auto& currentFrag : currentFrags) {
            // Check if this fragment needs further fragmentation for the current MTU
            if (currentFrag.dataLength + IP_HEADER_SIZE <= mtu) {
                // No further fragmentation needed for this fragment, pass it through
                nextFrags.push_back(currentFrag);
            } else {
                // This fragment IS too large and needs to be split
                int remainingData = currentFrag.dataLength;
                int currentOffsetBytes = currentFrag.offsetBytes;

                while (remainingData > 0) {
                    // Determine data size for the new smaller fragment
                    int dataForNewFrag = std::min(remainingData, maxDataPayload);

                    ProcessingFragment newFrag;
                    newFrag.dataLength = dataForNewFrag;
                    newFrag.offsetBytes = currentOffsetBytes;

                    // Determine the MF flag for the new fragment:
                    // It's the last piece derived *from this currentFrag* if remainingData equals dataForNewFrag.
                    bool isLastPieceOfCurrentFrag = (remainingData == dataForNewFrag);
                    // If it IS the last piece, it inherits the MF flag of the fragment being split.
                    // If it's NOT the last piece, its MF flag MUST be true (1).
                    newFrag.moreFragments = isLastPieceOfCurrentFrag ? currentFrag.moreFragments : true;

                    nextFrags.push_back(newFrag);

                    // Update for next iteration within this fragment's split
                    remainingData -= dataForNewFrag;
                    currentOffsetBytes += dataForNewFrag;
                } // end while (splitting currentFrag)
            } // end if (needs fragmentation)
        } // end for (each currentFrag)

        // The fragments for the next step are the ones generated in this step
        currentFrags = std::move(nextFrags); // Use move for efficiency

    } // end for (each mtu in pathMTUs)


    // --- 3. Convert Final Processing Fragments to Output Format ---
    std::vector<Fragment> resultFragments;
    for (const auto& finalProcessingFrag : currentFrags) {
        Fragment finalFrag;
        finalFrag.length = finalProcessingFrag.dataLength + IP_HEADER_SIZE; // Total length
        finalFrag.offset = finalProcessingFrag.offsetBytes / 8;          // Offset in 8-byte units
        resultFragments.push_back(finalFrag);
    }

    return resultFragments;
}

// --- Example Usage (Optional) ---
#include <vector>
#include <iostream>

void printFragments(const std::string& title, const std::vector<Fragment>& fragments) {
    std::cout << title << ":" << std::endl;
    if (fragments.empty()) {
        std::cout << "  (No fragments)" << std::endl;
        return;
    }
    int i = 1;
    for (const auto& frag : fragments) {
        std::cout << "  Fragment " << i++ << ": Length=" << frag.length
                  << ", Offset=" << frag.offset << " (Bytes=" << frag.offset * 8 << ")" << std::endl;
    }
     std::cout << "--- Total Fragments: " << fragments.size() << " ---" << std::endl;
}

int main() {
    // Example 1: Simple fragmentation
    int packetLen1 = 1500; // Typical Ethernet payload size (1480 data + 20 header)
    std::vector<int> mtus1 = {1500, 576, 1500}; // Path: Ethernet -> Smaller Link -> Ethernet
    try {
        std::vector<Fragment> frags1 = fragmentPacket(packetLen1, mtus1);
        printFragments("Example 1 (1500B packet, MTUs: 1500, 576, 1500)", frags1);
        /* Expected Output (MTU 576 -> max data (576-20)=556 -> aligned 552):
           Frag 1: Len=572 (552 data), Offset=0
           Frag 2: Len=572 (552 data), Offset=69 (552/8)
           Frag 3: Len=396 (376 data), Offset=138 (1104/8) -> 1480 - 552 - 552 = 376
        */
    } catch (const std::invalid_argument& e) {
        std::cerr << "Example 1 Error: " << e.what() << std::endl;
    }

    std::cout << "\n---------------------------\n" << std::endl;

    // Example 2: From Problem 6 (approximate, using the final calculated values)
    int packetLen2 = 24 * 1024; // 24KB
    std::vector<int> mtus2 = {4352, 2346, 1500, 4464, 2346}; // Path MTUs from problem 6 (assuming FDDI=4352)
     try {
        std::vector<Fragment> frags2 = fragmentPacket(packetLen2, mtus2);
        printFragments("Example 2 (24KB packet, MTUs: 4352, 2346, 1500, 4464, 2346)", frags2);
         /* Expected Output (Based on final MTU 1500 -> max data 1480):
            Should result in 17 fragments.
            16 fragments of Length=1500, Offset=0, 185, 370, ..., 2775
            1 fragment of Length=896, Offset=2960 (data=876)
         */
    } catch (const std::invalid_argument& e) {
        std::cerr << "Example 2 Error: " << e.what() << std::endl;
    }

     std::cout << "\n---------------------------\n" << std::endl;

    // Example 3: Invalid MTU
    int packetLen3 = 100;
    std::vector<int> mtus3 = {1500, 68, 50}; // MTU 50 is <= HEADER_SIZE+8 effectively
     try {
        std::vector<Fragment> frags3 = fragmentPacket(packetLen3, mtus3);
        printFragments("Example 3 (100B packet, MTUs: 1500, 68, 50)", frags3);
    } catch (const std::invalid_argument& e) {
        std::cerr << "Example 3 Error: " << e.what() << std::endl; // Expected error
    }


    return 0;
}